package airthmetic.exercise.dp;

public class _337_打家劫舍III {
    public int rob2(TreeNode root) {
        int[] res = recur2(root);
        return Math.max(res[0], res[1]);
    }

    public int[] recur2(TreeNode root){
        if(root == null){
            return new int[2];
        }
        int[] res = new int[2];
        int[] left = recur(root.left);
        int[] right = recur(root.right);
        res[0] = Math.max(left[1], left[0]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;

    }



    public int rob(TreeNode root) {
        /**
         典型的树形dp问题
         首先不管怎么样，都需要遍历整棵树才能求解问题
         这里选后序遍历，因为求解root时需要左右子树的结果才能确定抉择

         动态规划思考问题
         重叠子问题：树的某个节点最多能偷盗多少钱
         无后效性：树的某个节点最多能偷盗多少钱不会被后续求解破坏
         最优子结构：树的某个节点最多能偷盗多少钱是相互独立子问题，并且树的某个节点最多能偷盗多少钱可以被后续问题求解时使用

         1.确定状态参数和选择
         状态参数：当前节点最多能偷盗多少钱

         2.定义dp table
         int[] dp = new int[2];
         dp[0] 表示当前房间不偷盗最多能偷到多少钱
         dp[1] 表示档期那房间偷盗最多能偷到多少钱

         3.初始化 dp table
         dp[0] = 左右子节点金额偷盗之和
         dp[1] = 左右子节点不偷盗 + 当前节点偷盗节点之和
         4.推导状态转移公式
         dp[0] = Math.max(left(偷), left(不偷)) + Math.max(right(偷), right(不偷));
         dp[1] = current + left(不偷) +right(不偷);
         */



        int[] dp = recur(root);
        return dp[0] > dp[1] ? dp[0] : dp[1];
    }

    public int[] recur(TreeNode root){
        // terminal
        if(root == null){
            return new int[2];
        }

        int[] dp = new int[2];
        // process current logic
        int[] left = recur(root.left);
        int[] right = recur(root.right);
        dp[0] = Math.max(left[1], left[0]) + Math.max(right[1], right[0]);
        dp[1] = root.val + left[0] + right[0];

        return dp;
    }
}
